The present invention relates to a device for following and recursively estimating the local state of picture contours, particularly for the purpose of the adaptive prediction for the differential coding of television signals.
Coding using differential pulse code modulation (DPCM) has already been the subject of numerous study, published more particularly in the following articles:
"Predictive Quantizing Systems (Differential Pulse Code Modulation) for the Transmission of Television Signals" by J. B. O'Neal, published in the American Journal "Bell System Technical Journal", Vol. 45, pages 689 to 721, May 1966.
"System for the Numerical Coding of the Television Picture--the OCCITAN Project", by J. PONCIN and J. SABATIER published in the French Journal "L'echo des recherches", Jan. 1976, pp. 28 to 37. "Degradation of image signals and subjective quality in digital coding: visibility of the contour flutter" by F. KRETZ and J. L. Boudeville, published in the French Journal "Annales des Telecommunications", Vol. 31, No. 9-10, September/October 1976.
In DPCM coding, the difference between the real value of a television signal sample and a prediction (estimate) of this value calculated on the basis of prior close coded samples is coded. This difference is quantized and coded. Numerous studies have been carried out on the quantization characteristic. Conventionally it is unique and symmetrical with respect to the value 0, but other types of quantization have been envisaged and are for example described in the following documents:
French Pat. No. PV 77 26773 "Compression and expansion (Quantization) of numerical television signals with differential coding", inventors F. KRETZ and J. L. BOUDEVILLE.
"Optimization of DPCM video scheme using subjective quality criterion", by F. KRETZ and J. L. BOUDEVILLE amd P. SALLIO, published in the reports of the IERE Conference, No. 37, September 1977, pp. 185-194. First Certificate of Addition to Pat. No. PV 78 26773, referred to hereinbefore, PV 78 35485, inventors J. KRETZ and J. L. BOUDEVILLE. "A DPCM system with bidimensional predictor and controlled quantizer", by T. KUMMEROW, published in the reports of "TAGUNGSBERICHT NITG-FACHTAGUNG: Signalverarbeitung", April 1973, ERLANGEN, pp. 425-439. "Adaptive quantization of picture signals using spatial masking" by A. NETRAVALI and B. PRAVADA, published in the American Journal "Proceedings of the IEEE", April 1977, pp. 536-548.
With regard to the digital transmission of a television signal, the Union Europeenne de Radio-diffusion provided for the use of a transmission system standardized by CCITT with a flow rate of 34 Mbit/s. It was possible to realise such a system by separately coding the components and by using the invention described in the First Certificate of Addition to the aforementioned patents for coding the luminant signal. Thus, a good quality of the restored pictures was obtained.
For this application, it is useful to attempt to further improve the quality obtained by more complex coding. For other applications, it can be useful to reduce the flow rate to the minimum possible value according to conventional methods, whilst retaining a given quality.
Much research was carried out with this objective leading to an adaptive prediction. Reference is for example made to the following articles: "Predictive quantizing of television signals" by R. E. GRAHAM, published in the reports to IRE Wescon Convention record, Vol. 2, part 4, 1958, pp. 147 to 157. "DPCM picture coding with adaptive prediction" by W. ZSCHUNKE published in the American Journal IEEE Tr on Com., Vol. COM 25, No. 11, November 1977, pp. 1295 to 1302.
In this research, the prediction is selected from a number of predictions, each corresponding to the value of a prior point close to the point to be coded or to a simple linear combination of the prior values of close points to the point to be coded. Each prediction is adapted to a given local orientation of the picture (i.e. to the case of a contour of this orientation passing in the vicinity of the point to be coded). A decision organ estimates the local orientation and as a result selects the appropriate prediction. The two last-mentioned studies referred to hereinbefore use estimates based on simple tests on the differences between prior points close to the point to be coded.
Before defining the invention, a number of definitions will be given with respect to the motions and magnitudes relating to the treated pictures.
The invention more essentially applies to images formed from lines of equidistant points disposed in the centres of rectangles formed by a double group of orthogonal lines and which is generally called "orthogonal sampling structure". The invention also applies to the case of a "staggered field sampling structure" (cf article by J. SABATIER and F. KRETZ entitled "The sampling of the components of 625 line colour television signals", published in the UER Technical Journal, No. 171. October 1978, pp. 212 to 215). FIG. 1a illustrates this structure. All the lines are assumed to contain N points which, in the case of application to television images, are the end points forming a line of the video signal, the number of lines being dependent on the adopted standard. Each point of the line is characterized by an optical quantity, namely either the luminance, or the chromaticity, or any other signal of this type (e.g. the luminant signal or the difference signals). This quantity is determined by the sampled electrical signal X with different marks or accents.
When two adjacent points have an amplitude difference which exceeds a certain threshold, there is "a picture contour element", which is horizontal if the two points are next to each other and vertical if the two points are one below the other. Each element of the contour is represented, as in FIG. 1, by a line between the two points in question and designated EH for the first and EV for the second.
Two horizontal or vertical contour elements are said to be connected if two of their ends are connected. Thus, a contour is defined by a system of connected contour elements or by the system of points adjacent thereto. The average contour curve represents in some way the location of points of the same amplitude for example of the same lighting intensity. The contours shown in exemplified manner in FIG. 1a has 6 vertical contour elements and 4 horizontal contour elements.
At all points, such a contour has an average orientation which is given by the tangent to the mean curve of the contour. This orientation is taken with respect to the vertical and is designated .theta.. One of the objects of the invention relates to the estimation of this orientation for each line.
Naturally, all the contour elements of one picture are not necessarily connected and certain of them can be isolated. In the line by line following of contours and their observation in each line, significance is attached to the contour elements belonging to one and the same line and which are connected. Such elements from systems called "connected zones". FIG. 1a shows a connected zone, considered as an integral part of a contour. It starts by a first contour element (in the present case a horizontal element) and finishes by a final contour element (in the present case a vertical element). The latter element indicates the end of a connected zone. One point of the picture can belong to a connected zone and in the opposite case it is located in a "hole".
In the current or present line, the "past" of the observed contour is summarized by certain quantities necessary for following the contour and for the estimation of the local orientation. All these quantities constitute the "state" of the contour and is designated E. They are:
H and V: the average number of horizontal and vertical contour elements filtered recursively during the following or tracking of the contour; PA0 NM: the number of prior operations observed during the following of the contour; PA0 NP: the number of vertical contour elements, but which are not connected to horizontal contour elements observed in the lines preceding the line being processed; PA0 NS Partial sum of the signs observed S during the following of the contour, a distinction being made between its absolute value .vertline.NS.vertline. and its sign S, called the contour sign; PA0 Q; counts the observed sign inversions (S. S&lt;O) with a view to an interruption test of the following of the contour.
In certain cases, two or more than two contours can intercept to form a figure which is called a "fork". The two contours forming a fork each have a state (E' and E.sub.i ') from which can be extracted at the intersection point a state which will be "interpolated" and designated E.
As in the scanning of television pictures, the examination of a picture takes place line by line and point by point.
FIG. 1a shows the geometrical distribution of the present point and adjacent prior points, whilst FIG. 1c shows the angular convention used for the orientations (.theta. from -.pi./2 to +.pi./2, .theta.&gt;0 in the drawing) and their discretization.
FIG. 1b shows the position of various points which will be used with the notations: X.sub.n for the values to be coded, X.sub.n for the decoded values, the prime in X.sub.n ' designates the points of the preceding line and will in general designate signals carrying data corresponding to the preceding line. For the present or current line, consideration will be given to the current point at time n, (X.sub.n) or a time n+1 (X.sub.n+1) in certain cases, so that the final decoded point is X.sub.n.
FIG. 1c shows the angular convention (.theta. is considered relative to the vertical and is positive in the drawing, as well as the discretization of the angles which, in the present embodiment (table VI-a) has three module bits and one sign bit. In the drawing, the followed contour at the point of rank n-J has an estimated orientation .theta. of discretized value +1. The prediction is prepared on the present line for the following line by calculating a linear combination defined by .theta. of the values of X.sub.n-J and X.sub.n-J+1 which concern a point defined by .theta. in the following lines.